import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM56 有重复项数字的全排列
 * <a href="https://www.nowcoder.com/practice/a43a2b986ef34843ac4fdd9159b69863?tpId=295&tqId=700&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2023-03-02
 * Time: 23:38
 */
//这道题的解题思路和<牛客网：BM58 字符串的排列>这道题的解题思路一摸一样，
//具体解题思路在git的那道题中有详细解释，这里不做重复解释，因此注释较少。
public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        //判空处理
        if (num.length == 0);
        //排序，为了应对重复的元素和字节序
        Arrays.sort(num);
        //标记数组
        boolean[] flag = new boolean[num.length];
        ArrayList<Integer> buffer = new ArrayList<>();
        recursion(res,buffer,num,flag);
        return res;
    }

    private void recursion(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> buffer, int[] num, boolean[] flag) {
        if (buffer.size() == num.length) {
            //这一步切不可写成res.add(buffer)--细品
            res.add(new ArrayList<>(buffer));
        } else {
            for (int i = 0; i < num.length; i++) {
                if (flag[i]) {
                    continue;
                }
                if (i > 0 && num[i-1] == num[i] && flag[i-1]) {
                    return;
                }
                buffer.add(num[i]);
                flag[i] = true;
                recursion(res,buffer,num,flag);
                buffer.remove(buffer.size()-1);
                flag[i] = false;
            }
        }
    }
}
